/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-11-09
 * Time: 23:07
 */
class Solution {

    public int row;
    public int col;

    public int minimumEffortPath(int[][] heights) {
        row = heights.length;
        col = heights[0].length;
        int min = heights[0][0];
        int max = heights[0][0];
        // 找到最大差值
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                min = Math.min(min, heights[i][j]);
                max = Math.max(max, heights[i][j]);
            }
        }
        int left = 0;
        int right = max - min;
        while (left < right) {
            int mid = ((right-left) >> 1) + left;
            int[][] temp = new int[row][col]; // 用来标记这个位置是否已经走过
            if (!dfs(heights, temp, 0, 0, mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }



    int[][] next = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public boolean dfs(int[][] heights, int[][] mark, int x, int y, int val) {
        if (x == row-1 && y == col-1) {
            return true;
        }
        mark[x][y] = 1; // 标记一下已经走过
        for (int i = 0; i < 4; i++) {
            int nextX = x + next[i][0];
            int nextY = y + next[i][1];
            if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col
                    || mark[nextX][nextY] == 1
                    || Math.abs(heights[nextX][nextY] - heights[x][y]) > val) {
                // 越界了   已经走过了   高度差太大了 都不能再遍历了
                continue;
            }
            if (dfs(heights, mark, nextX, nextY, val)) {
                return true;
            }
        }
        return false;
    }
}
